package com.zklh.leetcode.top100.problem287;

/**
 * 寻找重复数算法实现 解法1, 二分查找实现
 *
 * @version 1.0
 * @Author tongnan
 * @Date 2023/12/18
 */
public class Solution1 {

    public int findDuplicate(int[] nums) {
        int l = 1, r = nums.length - 1;

        while (l < r) {
            int middle = (l + r) >> 1;
            int cnt = 0;
            for (int num : nums) {
                cnt += num <= middle ? 1 : 0;
            }

            if (cnt <= middle) {
                l = middle + 1;
            } else {
                r = middle;
            }
        }
        return r;
    }
}